class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        // enum a
        for (int first = 0; first < n; first++) {
            // a需要和上一次枚举的数不同
            if (first > 0 && nums[first] == nums[first - 1]) 
                continue;
            
            // 初始化c到最右边
            int third = n-1;
            int target = -nums[first];

            for (int second = first + 1; second < n; second++) {
                // b需要和上一次枚举的数不同
                if (second > first + 1 && nums[second] == nums[second-1])
                    continue;
                
                // 保证b在c左边
                while (second < third && nums[second] + nums[third] > target)
                    --third;
                
                if (second == third) 
                    break;
                
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]); 
                    list.add(nums[second]); 
                    list.add(nums[third]);
                    ans.add(list); 
                }
            }
        }
        return ans;
    }
}